#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define eb emplace_back
#define fi first
#define se second
using vec = vector < int >;

mt19937 rnd(19491001);

void report(int x, int y) { return Bridge(min(x, y), max(x, y)); }

void solve(vec pot, int u) {
	int v = pot[rnd() % pot.size()];
	unordered_map < int, vec > g;
	vec chain;
	for(auto t : pot) {
		if(t == v) continue;
		int x = Query(t, v, u);
		if(x == t) chain.eb(x);
		else g[x].eb(t);
	}
	sort(chain.begin(), chain.end(), [&](int x, int y) { return Query(x, y, u) == x; });
	int lst = u; for(auto v : chain) report(lst, v), lst = v;
	report(lst, v);
	for(auto &pot : g) 
		if(pot.se.size()) solve(pot.se, pot.fi);
}

void Solve(int N) {
	vec pot; for(int i = 1; i < N; i++) pot.eb(i);
	solve(pot, 0);
}
